This application relates to artificial intelligence and expert systems and, more particularly, to rule-based expert systems.
An expert system is a data processing system that attempts to duplicate a decision process used by a human expert when performing a complex task. Expert systems have been designed, for example, to design circuit board layouts, to configure computer systems, to perform scheduling on a factory floor, and so on.
In the fields of configuration and scheduling, there are usually recognized human "experts". These experts often have two sets of information based on experience that enable them to effectively and efficiently perform a task. First, the experts usually possess a set of "rules of thumb" about how the task should be performed. Second, the experts understand under what circumstances each rule of thumb should be applied. Expert systems often encode the "rules of thumb" knowledge of a human expert as a series of "rules" having a format as follows:
IF conditions THEN actions.
The "conditions" portion of a rule specifies one or more conditions or tests. If all tests in the conditions portion of a rule are true, then the actions portion of the rule can be performed, as described below. For example, a rule in a system that schedules jobs in a factory may include a rule such as:
IF PA0 THEN
there is a MACHINE with a STATUS of BROKEN and PA1 a STATUS of UNSCHEDULED requiring that machine PA1 set the STATUS of the JOB to NOT-SCHEDULABLE.
In this example, if a machine is broken, then the system will not schedule jobs that require the broken machine, and a status of "NOT-SCHEDULABLE" will be recorded for the job. Other rules in the system will indicate what is to be done when a job is not-schedulable.
The conditions portion of a rule is also called the "Left Hand Side" of the rule (abbreviated "LHS") or the predicate portion. The actions portion of a rule is also called the "Right Hand Side" of the rule (abbreviated "RHS"). Execution of the actions portion of a rule is also called "firing the rule".
To emulate an expert's application of these types of knowledge, conventional expert systems include a mechanism to determine, based on the information available, the appropriate sequence of rule activation. This mechanism is commonly referred to as the "inference engine".
Rule-based expert systems have been effective in solving problems which require large amounts of expertise. When compared to the problem being automated, expert systems are much more similar in structure and flow of control to human intuition than are programs created using standard "procedural" languages, such as Pascal or FORTRAN. As a result, the expert systems have been easier to conceive, develop, and maintain than functionally identical systems developed using standard programming languages.
In addition, expert systems have enabled automation of problems previously considered intractable. Programs (for example, Digital Equipment Corporation's XCON, a program for configuring computer systems) have been successfully implemented using expert systems techniques when efforts using standard techniques had failed.
The success of expert systems can be traced to two concepts that differentiate rule-based programming from standard programming. These two concepts are: global memory and non-procedural execution, as described below.
Conventional rule-based programming uses a global memory, usually referred to a "working memory". Working memory contains all the information available to the rules for testing conditions. All rules can test any information in working memory. Conversely, once information has been put into working memory, it is visible to all rules. This working memory differs from that of standard programming languages, where there is a distinct mapping (scope) defining which data is visible to which executable statements.
Moreover, in rule-based programming, rules are the only type of executable statement. Unlike standard languages where the sequence of execution is based on the sequence of executable statements in a program, sequence of rule executions is based on decisions made by the inference engine concerning eligibility of a rule to fire. This process of determining eligibility and executing a rule is called the recognize-act cycle. In the recognize step, a rule is selected based on information in working memory and according to the strategy incorporated in the inference engine. In the act step, the RHS of the selected rule is executed. These two steps are repeated until there are no rules eligible to be executed, or until a rule indicating a Halt action is executed. The recognize-act cycle is described below in more detail.
The concepts of global memory and non-procedural execution make it possible for conventional rule-based systems to closely emulate the actions of a human expert. Working memory contains all the information available to the expert. For example, in the shop floor scheduling example above, the working memory contains information identifying the machines available for scheduling and the jobs needing to be scheduled. Thus, rule-based, non-procedural execution is a much closer analog to the decision process of a human expert, where decisions about what should be done next are highly situation dependent.
There are at least two problems that limit the effectiveness and range of conventional rule-based programming. These are: complexity and embedability, as discussed below.
Because all information in a conventional rule-based system is global, program complexity, as measured by the number of potential interactions between separate parts of the program, tends to grow exponentially as program size grows linearly. There are numerous problems for which rule-based programming is appropriate that are small in size and, therefore, do not have problems with complexity. There are also problems of significant size that can be solved with rule-based programming, but are difficult to develop and maintain because of the resulting complexity.
The problem of complexity is not unique to rule-based programming. Standard, procedural, programming languages solve the problem of complexity through modularization. To reduce complexity, large programs are modularized, i.e., partitioned into modules. Each module is smaller, and less complex than the total system, with a well-defined interface to the other modules. A module can be built or modified without having to understand the entire program and can be more easily re-used or shared when appropriate. This reduction in size, combined with a better specification of module inter-dependence, reduces complexity.
The software engineering concept of modularity has traditionally been considered to be in direct conflict with the principles underlying rule-based programming. Although some rule-based languages have incorporated modularity concepts, these languages have retained few of the original benefits of a rule-based language. These languages eliminate the concept of global memory, and do not allow sharing of data between modules.
As mentioned above, another problem of conventional rule-based programming is a lack of embedability, i.e., integration of rule-based systems with programs written in standard, procedural languages. Rule-based programming is not suitable for all tasks. There are numerous tasks that are procedural in nature, for which procedural programming is more appropriate than rule-based programming In most large systems, there is a portion of the solution that is best addressed by procedural programming, and a portion best addressed by non-procedural programming. Existing rule-based programming languages are difficult and, in some cases impossible, to integrate with procedural languages because rule-based languages usually lack callable entry points that the procedural program can use to call the rule-based program.
Conventional rule-based programming lacks appropriate mechanisms to manage the complexity of rule-based systems and for embedding these expert systems in procedural systems, as needed.